The present invention relates to computers and, more particularly, to computer communications-interface devices. A major objective of the invention is to provide for FIFO systems that permit simple detection of xe2x80x9cfullxe2x80x9d and xe2x80x9cemptyxe2x80x9d conditions when using read and write pointers with modulo numbers that are not powers of two.
Much of modern progress is associated with advances in computer technology. As computers have become more powerful, they have been required to communicate increasingly with peripherals and other computers. Buffering can facilitate asynchronous communications and thus obviate a need for communicating devices to share a common time base. In addition, buffering computer communications allows a host computer to attend to other tasks on a time-multiplexed basis during a communications session.
Buffering is commonly accomplished using RAM-based FIFOs, a first-in-first-out (FIFO) device in which data being communicated is temporarily stored in random-access memory (RAM). When a suitable unit, e.g., byte, of data is received by the FIFO, the data unit is stored at a FIFO address indicated by a write pointer. Once that data is stored, the write pointer is incremented to the next addressxe2x80x94which is where the next unit of data received will be stored. When a device is ready to read from the FIFO, it reads from a FIFO address indicated by a read pointer. After the data is read, the read pointer is incremented so that the next read is from the next FIFO address. Each pointer is basically a counter that counts data transfers. The counters are modulo in that they wrap to zero when a maximum count is reached.
Reading from a FIFO is typically stopped when the FIFO is empty and writing to the FIFO is typically stopped when the FIFO is full. In some FIFO systems, the read and write pointers have modulo numbers twice the FIFO depth. In such a case, xe2x80x9cemptyxe2x80x9d is indicated when the pointers are equal, and xe2x80x9cfullxe2x80x9d is indicated when the difference between the pointers is the FIFO depth, which is half the pointer modulo number. In binary counters are used, the FIFO is either full or empty when all the bits except the most significant bit are equal; the most significant bit distinguishes between full and empty. The following pairs of 3-bit modulo-8 binary values (with decimal equivalents) indicate a xe2x80x9cfullxe2x80x9d FIFO with four storage locations: 000 (0), 100 (4); 001 (1), 101 (5); 010 (2), 110 (6); and 011 (3), 111 (7).
Conventional binary-code counters can be used as FIFO pointers. Binary counter design has matured to the point where, once a few specifications (such as target modulo number) are entered, a computer can yield an optimized counter design. A disadvantage of binary counters is that there can be considerable ambiguity when a count is read during a count transition. For example, when a count increments from 011=3 to 100=4, every bit value changes. However, the changes can take place at slightly different times across the bit positions. Any of eight possible 3-bit binary values might be read during this transition. Attempts to design around such extreme ambiguities can add considerable complexity to the counter or to circuit elements that respond to the counter.
An alternative to binary code called xe2x80x9cgray codexe2x80x9d requires a change in only one bit position in the event of a unit increment. The following is a 3-bit gray code sequence: 0=000, 1=001, 2=011, 3=010, 4=110, 5=111, 6=101, 7=100. Incrementing the last value, 100, yields the first value 000. Since only one bit position changes during a unit increment, the only possible reads during a transition are the value being changed from and the value being changed to. It is much easier to design around this limited ambiguity than it is to design around the much more extensive ambiguities confronting binary counter reads. Gray codes can readily be constructed for any bit length. A one-bit gray code can be the same as a one-bit binary code. The sequence is 0,1. A two-bit gray code can be derived from a one-bit gray code by the following three-step algorithm. First, the sequence is copied to yield 0,1;0,1. Second, the replica is reversed to yield 0,1;1,0. Third, leading zeroes are added to the values in the original and leading ones are added to the reversed values of the inverted replica to yield 00, 01, 11, 10. This is a two-bit gray code. The three-step algorithm can be applied to the two-bit gray-code to yield the three-bit gray code described above. The algorithm can be iterated to yield gray codes of any desired bit length.
Despite representing an alternative encoding scheme for umbers, gray code shares with binary code the characteristic that counts one-half the power-of-two counter modulus apart are readily determined. If two counts differ at and only at both of their two most-significant bits, they are spaced apart by one-half the counter modulo number of counts apart. For example, two 3-bit modulo-8 gray-code counts are four counts apart when they are the same in their least-significant bit and different in the two most-significant bits. The xe2x80x9cfullxe2x80x9d gray-code pairs (with decimal equivalents) are 000 (0), 110 (4); 001 (1), 111 (5), 011 (2), 101 (6), 010 (3), 100 (7). Thus, read and write counters based on power-of-two gray-code counters provide facile detection of full and empty FIFO conditions.
A problem with many gray-code counter designs is that they tend to be complex and are not readily scaled. These problems are addressed by a gray-code design disclosed by Wingen in U.S. Pat. No. 5,754,614. Wingen""s gray-code counter comprises a count register for storing a gray-code count, a gray-code decoder for converting the stored gray-code count to a corresponding binary-code value, a binary-code incrementer for incrementing the binary-code value, and a gray-code encoder for converting the incremented binary-code value to the corresponding gray-code count.
A disadvantage of the Wingen gray-code counter as well as other gray-code counters (e.g., those referenced in the Wingen patent) is that, when the target FIFO depth is not a power of two, the FIFO design has excess capacity. For example, when a communication application only requires a FIFO depth of 78, the power-of-two limitation requires the use of an 128-address FIFO. In contrast, binary-code counters can be designed for any positive-integer depth. The discrepancy between target and gray-code-imposed capacities can be much greater for larger FIFOs. The excess capacity can be costly in terms of integrated-circuit area that might otherwise be devoted to other functions. The incorporating integrated circuit can be less functional or more costly as a result.
Parent U.S. patent application Ser. No. 09/434,218 addresses excess capacity by disclosing a scaleable design for non-power-of-two even modulo gray-code counters. However, when the disclosed counters are one-half their modulo apart in their gray-code counts, the gray-code counts typically do not differ in any simple fashion. For example, in a 3-bit modulo 6 counter (Table I of U.S. application Ser. No. 09/434,218) the pairs that are three counts apart are: 000 (0), 010 (3); 001 (1), 110 (4); and 011 (2), 100 (5). Thus, it is not straightforward to determine when a FIFO is full when two such counters are used for the read and write pointers. What is needed is a scaleable non-power-of-two gray-code counter design that provides for simple determination of when two counts are half the counter modulo apart.
The present invention provides an n-bit modulo-M gray-code counter in which the distribution of M gray-codes among N=2**n possible n-bit gray codes has bilateral symmetry. Preferably, the symmetry is translational, but it can also be reflective or both. In a FIFO or other system having two such gray-code counters, detecting xe2x80x9cfullxe2x80x9d conditions in which the counts are M/2 counts apart is readily achieved using either the gray-code count or binary-code equivalents.
A suitable gray code can be constructed for any selected modulo number that is divisible by four in the following manner. Start with a power-of-two gray code for the next larger power of two. For example, if xc2xdN less than M less than N, select the full n-bit modulo-N gray code. Then omit (skip) (Nxe2x88x92M)/4 gray codes at the beginning of the modulo-N gray-code sequence, (Nxe2x88x92M)/2 gray codes in the middle of the modulo-N gray-code sequence, and (Nxe2x88x92M)/4 gray codes at the end of the modulo-N gray-code sequence. The result is a modulo-M gray code sequence.
For example, a modulo-12 gray code can be constructed from a modulo-16 gray code as indicated: 0123456789ABCDEF, where the gray codes are presented by hexadecimal-code equivalents, and the twelve included codes are underlined. Note that any two underlined modulo-12 values that are six underlined modulo-12 counts apart are separated by exactly one skip over two non-underlined values of the corresponding modulo-16 system. Thus, any two counts separated by six counts in the modulo-12 system are separated by eight counts in the corresponding modulo-16 system. Thus, the modulo-12 system can use the same detection scheme as the corresponding modulo-16 system. More generally, any non-power-of-two modulo-M system with bilateral translational symmetry can use the same detector design for full indications as the corresponding power-of-two modulo-N system.
While the foregoing method can generate gray-codes for any target modulus number that is divisible by four, there are other methods that can generate alternative gray codes with the desired symmetry. For example, select M/4 consecutive gray-code values from a set of N/4 gray codes. Apply the gray-code expansion technique (copy, flip, add 0s and 1s) twice, and the result is a modulo-M code with bilateral translational and reflective symmetry. Alternatively, one can select the first (or last) M/2 consecutive gray codes from a set of N/2 gray codes, apply the gray-code expansion technique once, and achieve a gray code with bilateral reflective symmetry but not bilateral translational symmetry.
A gray-code counter can include a gray-code decoder, a binary incrementer, a gray-code encoder, and a count register. The gray-code decoder takes present gray-code counts and translates them to xe2x80x9cpresentxe2x80x9d binary-code values. The binary incrementer increments the present binary-code values to yield successor binary-code values. The binary incrementer is designed to xe2x80x9cskip overxe2x80x9d binary values that have no equivalents in the modulo-M gray code. In the hexadecimal notation example above, an incrementer would increment from 6 to 9 (skipping 7 and 8), and would increment from E to 1 (skipping F and 0). The gray-code encoder converts the successor binary-code values into successor gray-code counts. When the register is next clocked, the successor gray-code counts overwrite their predecessors and become the present gray-code counts for the next iteration.
FIFO xe2x80x9cfullxe2x80x9d detections are readily obtained where the read and write pointers are counters with bilateral translational symmetric distributions. In fact, there is a choice of methods for determining a xe2x80x9cfullxe2x80x9d condition. The simpler xe2x80x9cfullxe2x80x9d -detection method involves comparing the gray-code counts. In that case, xe2x80x9cfullxe2x80x9d is indicated when the read and write counts differ at and only at their two most-significant bits. The alternative xe2x80x9cfullxe2x80x9d -detection method involves subtracting the binary-code equivalents of the gray-code counts. If the difference is N/2, i.e., half the modulo number for the corresponding power-of-two counter, the FIFO is full.
Thus, the present invention provides a scaleable non-power-of-two gray-code counter counter design with straightforward detection of FIFO xe2x80x9cfullxe2x80x9d conditions. As explained above, the invention provides at least two convenient methods of making the xe2x80x9cfullxe2x80x9d determinations. These and other features and advantages of the invention are apparent from the description below with reference to the following drawings.